package binaryTree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class IsBinaryTree {
    //迭代实现
    public boolean isBalanced(TreeNode root) {
        if (root==null){
            return  true;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (!list.isEmpty()){
            int size = list.size();
            while (size>0){
                TreeNode cur = list.poll();
                if (cur.left!=null){
                    list.add(cur.left);
                }
                if (cur.right!=null){
                    list.add(cur.right);
                }
                int leftHeight = maxDepth(cur.left);
                int rightHeight = maxDepth(cur.right);
                if (Math.abs(leftHeight-rightHeight)>1){
                    return  false;
                }
                size--;

            }
        }
        return   true;
    }

    public  int maxDepth(TreeNode root){
        //后序遍历  左右根来记录深度
        if (root==null){
            return  0;
        }
        int i = maxDepth(root.left);    //左边遍历
        int i1 = maxDepth(root.right);   //右边遍历
        return 1+Math.max(i,i1);    //根节点  处理
    }

//    递归实现
    public  static  boolean result=true;
    public boolean isBalanced1(TreeNode root) {
        if (root==null){
            return  true;
        }
      preOrderTraver(root);
         return  result;

    }

//这个递归的模式下  返回值为void    不然的话似乎不好处理
    public  void preOrderTraver(TreeNode root){
        if (root==null){
            return;
        }
        if (Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){
            result=false;
            return ;  //递归结束条件
        }
        preOrderTraver(root.left);
        preOrderTraver(root.right);
    }



    //代码随想录题解
    /**
     * 递归法
     */
    public boolean isBalanced2(TreeNode root) {
        return getHeight1(root) != -1;
    }

    private int getHeight1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public boolean isBalanced3(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root!= null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode inNode = stack.peek();
            // 右结点为null或已经遍历过
            if (inNode.right == null || inNode.right == pre) {
                // 比较左右子树的高度差，输出
                if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) {
                    return false;
                }
                stack.pop();
                pre = inNode;
                root = null;// 当前结点下，没有要遍历的结点了
            } else {
                root = inNode.right;// 右结点还没遍历，遍历右结点
            }
        }
        return true;
    }

    /**
     * 层序遍历，求结点的高度
     */
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
        }
        return depth;
    }



    public static void main(String[] args) {
        IsBinaryTree isBinaryTree = new IsBinaryTree();
        TreeNode root= new TreeNode(1);
        TreeNode treeNode1 = new TreeNode(2);
        root.left=treeNode1;
        System.out.println(isBinaryTree.isBalanced2(root));



    }




}
